# -*- coding: utf-8 -*-

'''
@author: 5822 - Duarte Marques & 5955 - João Rosa
@date: 06 de Junho de 2013
@obs: Trabalho de Estruturas de Dados e Algoritmos
      Docente: Prof. Jasnau Caeiro
'''

from random import uniform
from time import clock

class insertion_sort:
	'''
	Classe que contém o algoritmo Insertion_Sort.
	'''
	
	def __init__(self, A):
		'''
		Metodo onde inicializam algumas variaveis para
		serem utilizadas mais tarde.
		Recebe como parameto uma lista "A".
		'''
		self.A = A
		self.key = None
		
	def insertion_sort(self):
		'''
		Metodo que contem o algoritmo de ordenação 
		Insertion Sort.
		'''
		for j in xrange(1,len(self.A)):
			self.key = self.A[j]
			i = j - 1
			while i > -1 and self.A[i] > self.key:
				self.A[i + 1] = self.A[i]
				i = i - 1
				pass
			self.A[i + 1] = self.key
			pass
		#print self.A


# A = [7, 4, 9, 3, 6, 8, 1, 5, 2]

# print A

# g = insertion_sort(A)
# g.insertion_sort()

